﻿// Copyright (c) 2011, Adaptiv Design
// All rights reserved.
// 
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
//     * Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation and/or
// other materials provided with the distribution.
//    * Neither the name of the <ORGANIZATION> nor the names of its contributors may
// be used to endorse or promote products derived from this software without specific
// prior written permission.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
// IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
// INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;

using Alicanto.Lexing;

namespace Alicanto
{
    internal class Precedence
    {
        delegate TokenSequence SpecialOperatorHandler(TokenSequence tokens);

        static private IDictionary<Token, int> LEFT_PRESEDENCE = new Dictionary<Token, int> 
        {
            { Token.OpCall, 999 },
            { Token.OpMemberAccess, 999 },
            { Token.OpMultiply, 1 },
            { Token.OpSubtract, 0 },
            { Token.OpAdd, 0 },
            { Token.OpEqual, 0 }
        };

        static private IDictionary<Token, SpecialOperatorHandler> DEVIATIONS = new Dictionary<Token, SpecialOperatorHandler>()
        {
            { Token.OpCall, _handleOpCall },
            { Token.SquareBracketOpen, _handleSquareBrackets }
        };

        static private TokenSequence _sequence(TokenSequence tokens, Token tokenOpen, Token tokenClose)
        {
            TokenSequence result = new TokenSequence();
            result.Push(tokenOpen);

            TokenSequence element = new TokenSequence();

            int open = 1;
            while (tokens.Available > 0 && open > 0)
            {
                Token current = tokens.Pop();

                if (current == tokenOpen)
                    open++;
                else if (current == tokenClose)
                    open--;

                if (open == 0)
                    element.Push(Token.Comma);
                else
                    element.Push(current);

                if (open == 0 || (current == Token.Comma && open == 1))
                {
                    ApplyOperatorPrecedence(element);

                    // Transfer to result
                    while (element.Available > (open == 0 ? 1 : 0))
                    {
                        result.Push(element.Pop());
                    }
                }
            }

            if (open > 0)
                throw new Exception("Unclosed brackets");

            result.Push(tokenClose);
            return result;
        }

        static private TokenSequence _handleSquareBrackets(TokenSequence tokens)
        {
            return _sequence(tokens, Token.SquareBracketOpen, Token.SquareBracketClose);
        }

        static private TokenSequence _handleOpCall(TokenSequence tokens)
        {
            Token name = tokens.Pop(TokenType.SimpleName);
            if (tokens.Peek() == Token.BracketOpen)
            {
                tokens.Pop();
                TokenSequence result = _sequence(tokens, Token.BracketOpen, Token.BracketClose);
                result.Insert(name);
                return result;
            }
            else
            {
                return new TokenSequence(name);
            }
        }

        static internal void ApplyOperatorPrecedence(TokenSequence tokens)
        {
            TokenSequence output = new TokenSequence();

            // Reverse polish notation queue
            Queue<TokenSequence> rpn = new Queue<TokenSequence>();

            // Operator stack
            Stack<Token> operators = new Stack<Token>();

            while (tokens.Available > 0)
            {
                Token current = tokens.Pop();

                // + - / * ^
                if (current.Type == TokenType.Operator && LEFT_PRESEDENCE.ContainsKey(current))
                {
                    if ((operators.Count + rpn.Count) % 2 == 0)
                    {
                        // Make sure no parentheses are following
                        if (tokens.Peek() != Token.BracketOpen)
                        {
                            // Create a sequence containing this operator and the follow up token(s)
                            TokenSequence seq = null;

                            // This operator deviates
                            if (DEVIATIONS.ContainsKey(current))
                                // Get the deviating follow up
                                seq = DEVIATIONS[current](tokens);
                            // Follow up must be a literal of simple/special name
                            else if (tokens.Peek().Type == TokenType.Literal
                                || tokens.Peek().Type == TokenType.SimpleName
                                || tokens.Peek().Type == TokenType.SpecialName)
                                seq = new TokenSequence(tokens.Pop());
                            else
                                throw new Exception("Unexpected follow up");


                            // Insert the operator
                            seq.Insert(current);
                            rpn.Enqueue(seq);
                            continue;
                        }
                    }

                    if (operators.Count > 0)
                    {
                        int p1 = LEFT_PRESEDENCE[current];
                        if (LEFT_PRESEDENCE.ContainsKey(operators.Peek()))
                        {
                            int p2 = LEFT_PRESEDENCE[operators.Peek()];
                            if (p1 <= p2)
                            {
                                rpn.Enqueue(new TokenSequence(operators.Pop()));
                            }
                        }
                    }

                    operators.Push(current);

                    if (DEVIATIONS.ContainsKey(current))
                        rpn.Enqueue(DEVIATIONS[current](tokens));

                    continue;
                }
                // (
                else if (current == Token.BracketOpen)
                {
                    operators.Push(current);
                    continue;
                }
                // )
                else if (current == Token.BracketClose)
                {
                    while (operators.Count > 0 && operators.Peek() != Token.BracketOpen)
                        rpn.Enqueue(new TokenSequence(operators.Pop()));

                    if (operators.Count == 0)
                        throw new Exception("Unclosed parenthesis.");

                    // Pop (
                    operators.Pop();

                    continue;
                }
                else if (current.Type == TokenType.Structural && DEVIATIONS.ContainsKey(current))
                {
                    // Special case.
                    TokenSequence seq = DEVIATIONS[current](tokens);

                    if (rpn.Count == 0)
                    {
                        rpn.Enqueue(seq);
                    }
                    else
                    {
                        // Get last token sequence
                        TokenSequence last = null;
                        for (int i = 0; i < rpn.Count; i++)
                            if (i == rpn.Count - 1)
                                last = rpn.Dequeue();
                            else
                                rpn.Enqueue(rpn.Dequeue());

                        // Merge with last token sequence
                        while (seq.Available > 0)
                            last.Push(seq.Pop());

                        // Enque again
                        rpn.Enqueue(last);
                    }

                    continue;
                }
                // finalize
                else if (current.Type != TokenType.Literal 
                    && current.Type != TokenType.SimpleName 
                    && current.Type != TokenType.SpecialName)
                {
                    // Add remaining operators to rpn que
                    while (operators.Count > 0) rpn.Enqueue(new TokenSequence(operators.Pop()));

                    // Build output
                    Stack<TokenSequence> infix = new Stack<TokenSequence>();

                    while (rpn.Count > 0)
                    {
                        TokenSequence seq = rpn.Dequeue();

                        // Operator
                        if (seq.Available == 1 && seq.Peek().Type == TokenType.Operator)
                        {
                            Token op = seq.Pop();
                            if (LEFT_PRESEDENCE.ContainsKey(op))
                            {
                                TokenSequence sub = new TokenSequence();

                                // !! ORDER MATTERS
                                TokenSequence right = infix.Pop();
                                TokenSequence left = infix.Count > 0 ? infix.Pop() : new TokenSequence();

                                // (
                                sub.Push(Token.BracketOpen);

                                while (left.Available > 0) sub.Push(left.Pop());

                                sub.Push(op);

                                while (right.Available > 0) sub.Push(right.Pop());

                                // )
                                sub.Push(Token.BracketClose);


                                infix.Push(sub);
                            }
                        }
                        else
                        {
                            infix.Push(seq);
                        }
                    }

                    if (infix.Count == 1)
                    {
                        TokenSequence full = infix.Pop();
                        while (full.Available > 0)
                            output.Push(full.Pop());
                    }

                    if (infix.Count > 0)
                    {
                        throw new Exception();
                    }

                    output.Push(current);

                    while (tokens.Available > 0)
                        output.Push(tokens.Pop());

                    tokens.Update(output);
                    return;
                }

                rpn.Enqueue(new TokenSequence(current));
            }

            throw new Exception();
        }
    }
}
